package 笔试.广联达笔试.排序;

import java.util.ArrayList;
import java.util.Scanner;
//有一种排序算法定义如下：改排序算法每次只能把一个元素提到序列的开头，列如2,1,3,4.只需要一次操作把1提到起始位置就可以使得原序列从小到大排列。
//现在给你一个乱序的1-n的排列，请你计算最少需要多少次操作才可以使得原序列从小到大有序。
//输入描述：
// 输入的第一行包含一个正整数n，表示序列的长度（1<=n<=100000）
//接下来一行有n个正整数，表示序列中的n个元素，中间用空格隔开（1<=a_i<=n）
//感觉其实是求数组的逆序对
public class Main
{
    public static void main(String[] args)
    {
        //定义Scanner类
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();

//       String str = input.nextLine();
//       String[] strings=str.split(" ");
        ArrayList<Integer> integers = new ArrayList<>();
        int temp=0;
        while (temp<n&&input.hasNext())
        {
            integers.add(input.nextInt());
            temp++;
        }


//       for (int i = 0; i < strings.length; i++)
//       {
//           integers.add(Integer.parseInt(strings[i]));
//       }
        int[] nums = new int[integers.size()];
        for (int i = 0; i < integers.size(); i++)
        {
            nums[i] = integers.get(i);
        }

        Main main = new Main();
        System.out.println(main.reversePairs(n, nums));

    }

//    public static int sort(int n, int[] nums)
//    {
//        //对首位数的逆序对个数
//
//        if (n == 0 || n == 1)
//            return 0;
////        int firstNum = nums[0];
//        int count = 0;
//        for (int i = 0; i < nums.length; i++)
//        {
//            for (int j = i; j < nums.length ; j++)
//            {
//                if (nums[j] < nums[i])
//                    count++;
//            }
//
//        }
//        return count;
//    }
public int reversePairs(int n, int[] nums) {
    return merge(nums, 0, nums.length - 1);
}

    int merge(int[] arr, int start, int end) {
        if (start == end) return 0;
        int mid = (start + end) / 2;
        int count = merge(arr, start, mid) + merge(arr, mid + 1, end);

        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            count += arr[i] <= arr[j] ? j - (mid + 1) : 0;
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            count += j - (mid + 1);
            temp[k++] = arr[i++];
        }
        while (j <= end)
            temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, start, end - start + 1);
        return count;
    }




}
